home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / fish / 001-100 / 001-025 / 002 / xrf / xrf2.c < prev    next >
C/C++ Source or Header  |  1995-03-17  |  5KB  |  212 lines
  1.  
  2. /*
  3.  *                      ***************
  4.  *                      * X R F 2 . C *
  5.  *                      ***************
  6.  *
  7.  * This file contains the identifier tree and reference list management
  8.  * things. It uses a simple binary tree to store the identifiers for
  9.  * lookup and later sorted printing. Each node in the id tree has a
  10.  * pointer to the id string, left and right links and pointers to the
  11.  * beginning and end of the linked list of reference nodes for that
  12.  * id. Only the root of the tree is global, it is used by the sorted
  13.  * index printing function 'prtree'.
  14.  *
  15.  * Version V1.3          9-May-80
  16.  * Version V1.4        10-Jul-80 MM    Bummed code
  17.  * Version V1.5        23-Jul-80 MM    Redid storage code
  18.  * Version V1.6        23-Dec-80 RBD    Fixed bug in myalloc()
  19.  */
  20.  
  21. #include <stdio.h>
  22. #include "xrf.h"
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41. /*
  42.  * Tree search and insertion. This function returns a pointer to
  43.  * the new node if created. This may require some head scratching
  44.  * (I had to!). Look particularly at the significance of the pointer
  45.  * that is returned and how it is used by the recursive caller. If
  46.  * you want more, read "Algorithms + Data Structures = Programs"
  47.  * by Niklaus Wirth (Prentice Hall ISBN 0-13-022418-9) Chapter 4.
  48.  *
  49.  * It searches through the tree for a match to the supplied id (*kp).
  50.  * If it is found, a new reference node is linked into the list for
  51.  * that id. If no match is found, a new is node is inserted into the
  52.  * tree and appropriately initialized, including a first reference
  53.  * node.
  54.  *
  55.  */
  56.  
  57. struct idt *search(kp, link)            /* Function "search" */
  58. struct idt *link;                       /* Pointer to id node in tree */
  59. char *kp;                               /* Pointer to key string */
  60.    {
  61.    register struct idt *l;              /* Fast tree pointer */
  62.    register struct ref *r;              /* Fast list pointer */
  63.    register int cond;                   /* Condition from strcmp */
  64.    struct ref *newref();        /* Make reference function */
  65.    char *myalloc(); 
  66.  
  67.    if (debug) {printf("xrf: begin search\n");}
  68.    l = link;                            /* Copy link into register */
  69.    if(l == NULL)                        /* Not found, insert new id node */
  70.       {
  71.       l = (struct idt *)myalloc(sizeof(struct idt)); /* Make new ident node */
  72.       l->keyp = myalloc(strlen(kp)+1);    /* Get string space */
  73.                                         /* Fill in pointer to ... */
  74.       strcpy(l->keyp, kp);              /* ... stashed key string */
  75.       l->left = l->right = NULL;        /* No children */
  76.       l->first = l->last = newref();    /* Attach it to the id node */
  77.     if (debug) {printf("xrf: node insertion complete\n");}
  78.       }
  79.    else if((cond = strcmp(kp, l->keyp)) == 0) /* Match if true */
  80.       {
  81.     if (debug) {printf("xrf: found another reference at %d\n",lineno);}
  82.       r = newref();            /* Get a new ref. node */
  83.       l->last->next = r;        /* Hook new node into the list */
  84.       l->last = r;
  85.       }
  86.    else if(cond < 0) {                    /* Look left */
  87.     if (debug) {printf("xrf: looking left\n");}
  88.       l->left = search(kp, l->left);
  89.    } else {                                 /* Look right */
  90.     if (debug) {printf("xrf: looking right\n");}
  91.       l->right = search(kp, l->right);
  92.    }
  93.    return(l);
  94. }
  95.  
  96.  
  97. /*
  98.  * Initialize a line number referece
  99.  */
  100.  
  101. static struct ref *
  102. newref()
  103. {
  104.    char *myalloc();
  105.    register struct ref *r;
  106.  
  107.    if (debug) {printf("xrf: initializing line %d reference\n",lineno);}
  108.    r = (struct ref *)myalloc(sizeof(struct ref)); /* Make a reference node */
  109.    r->lno = lineno;                     /* Fill in line no. of ref. */
  110.    r->next = NULL;                      /* This is the end for now */
  111.    return(r);                /* Return pointer to the node */
  112. }
  113.  
  114. /*
  115.  * Storage allocation:
  116.  *
  117.  * my_free        Free byte pointer in local buffer
  118.  * my_left        Number of bytes left in local buffer
  119.  * my_link        Link of free space buffers (from malloc())
  120.  *
  121.  * If space can be gotten locally, get it.  If not, request a "large"
  122.  * chunk of memory and update my_free, my_left.
  123.  *
  124.  * My_link links chunks from monitor, myfree() returns them (called
  125.  * at a new input file).
  126.  */
  127.  
  128. struct my_alloc {
  129.     struct my_alloc    *my_next;
  130. };
  131.  
  132. static struct my_alloc    *my_link    = NULL;
  133. static char        *my_free    = NULL;
  134. static int        my_left        = 0;
  135.  
  136. char *myalloc(amount)
  137. int        amount;
  138. /*
  139.  * Allocate amount bytes.
  140.  */
  141. {
  142.     register char    *new;
  143.     register int    needed;
  144.     char        *malloc();
  145.  
  146.     needed = (amount + 1) & ~1;  /* Round up to a word bound */
  147.     if (needed > my_left) {
  148.         /*
  149.          * Gotta get storage
  150.          */
  151.         if ((my_free = malloc(512)) == NULL) {
  152.             quit();
  153.         }
  154.         my_left = 512 - (sizeof (struct my_alloc));
  155.         ((struct my_alloc *)my_free)->my_next = my_link;
  156.         my_link = (struct my_alloc *)my_free;
  157.         my_free += sizeof (struct my_alloc);
  158.     }
  159.     my_left -= needed;
  160.     if (my_left < 0) {
  161.         fprintf(stderr,"Trying to get too much: %d\n", needed);
  162.         exit(-1);
  163.     }
  164.     new = my_free;
  165.     my_free += needed;
  166.     return(new);
  167. }
  168.  
  169. myfree()
  170. /*
  171.  * Return all storage to the pool
  172.  */
  173. {
  174.     register struct my_alloc    *link;
  175.     register struct my_alloc    *next;
  176.  
  177.     next = my_link;
  178.     while ((link = next) != NULL) {
  179.         next = link->my_next;
  180.         free(link);
  181.     }
  182.     my_link = NULL;
  183.     my_free = NULL;
  184.     my_left = 0;
  185. }
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197. /*
  198.  * 'quit' handles dynamic memory deficit. (Sounds like U.S. Government!).
  199.  * It issues a polite message to the user, marks the list file for delete
  200.  * and exits to RSX.
  201.  *
  202.  */
  203.  
  204. quit()
  205.    {
  206.    puts("Not enough memory space, sorry.\n");
  207.    fclose(lst);
  208.    unlink(lst_name);
  209.    exit(1);
  210.    }
  211.  
  212.